package zuo.baseUP5_BigData;

/**
 * @Author: Forx
 * @Data: 2021/6/18
 * @Desc: Algorithm - zuo.baseUP5_BigData
 * @Version: v1.0
 */
public class main {
    /**
     * 1)哈希函数可以把数据按照种类均匀分流
     * 2)布隆过滤器用于集合的建立与查询，并可以节省大量空间
     * 3)一致性哈希解决数据服务器的负载管理问题
     * 4)利用并查集结构做岛问题的并行计算
     * 5)位图解决某一范围上数字的出现情况，并可以节省大量空间
     * 6)利用分段统计思想、并进一步节省大量空间
     * 7)利用堆、外排序来做多个处理单元的结果合并
     *
     *
     * */

    /**
     * 问题1
     * 32位无符号整数的范围是0~4,294,967,295,现在有一个正好包含40亿个无符号整数的文
     * 件，所以在整个范围中必然存在没出现过的数。可以使用最多1GB的内存，怎么找到所有
     * 未出现过的数？
     * 1GB = 2^30Byte = 2^28unsignedInt
     * 0-2^32-1 用位图做标记需要2^32/8 = 500MB 用1位表示一个数,够用
     *
     * 【进阶】
     * 内存限制为10MB,但是只用找到一个没出现过的数即可
     * 10M = 10*2^20Byte
     * 4KB呢
     * 这里解决4KB的
     * 4KB = 4*2^10B = 1024个 unsignedInt 那就申请int[512]剩余512做计算用
     * 2^32/512 = 8*1024*1024
     * 则遍历每一个数使得 int[data/(8*1024*1024)]++ (就是一个桶,看新进来的数属于那个范围然后对应的int++)
     * 最后数组中必然有一个元素是小于8*1024*1024的,那就再次遍历整个数据,这次只处理属于这个桶中的数据
     * 将这个桶中的数据再细分成512个范围,然后再统计那个少于8*1024*1024,之后再细分,如此细分下去总能找到少的那个数
     * 用这种方法的话,即便只有两个变量也能统计出来,假如两个变量就不断的二分.
     * */

    /**
     *
     * 32位无符号整数的范围是0~4294967295,现在有40亿个无符号整数,可以使用最多1GB的
     * 内存,找出所有出现了两次的数。
     * 依然可以用位图,不过这次因为要表现数量,要用两个bit来表示 00 0次 01 1次 10 2次 11 >=2次
     * 【补充】
     * 可以使用最多10MB的内存,怎么找到这40亿个整数的中位数
     * 方法同找缺失的数,不过这次是从左到右一次加词频,找到第一个大于20亿的索引,然后对这个范围继续细分
     * */
    /**
     * 有一个包含100亿个URL的大文件,假设每个URL占用64B,请找出其中所有重复的URL
     * 布隆过滤器
     * 哈希函数分流 - 按照哈希值分布到小文件里面,然后一个一个小文件来统计
     * 【补充】
     * 某搜索公司一天的用户搜索词汇是海量的(百亿数据量),请设计一种求出每天热门Top100
     * 词汇的可行办法
     * 外排 堆 败者树
     *
     * */


}
